\section{Анализ предметной области}
\subsection{Классификация основных типов ошибочных участков графа де Брюина}
Как уже не раз упоминалось, во входных данных, присутствует большое количество ошибок.

Основные типы ошибок:
\begin{itemize}
	\item \textit{Замена} отдельного нуклеотида на другой.
	\item \textit{Вставка/удаление} нуклеотида.
	\item \textit{Химерные риды} --- риды, составленные из различных участков генома, разделенных неизвестным расстоянием.
\end{itemize}

В зависимости от характера ошибки в риде, она может привести к образованию ошибочных участков различного вида (\cite{ZB08, CP08}). 

\begin{itemize}
\item Если ошибка в риде произошла в первом/последнем $k-1$ нуклеотиде, то в графе появится короткое ответвление, с одного из концов ``отделенное от графа''. Участок графа такого вида называют \textit{тупиком} (tip).

Если ошибка одна, то длина соответствующего тупика не превосходит $k$. Но так как ошибок в одном риде может быть несколько, то длина 
тупика может достигать длины рида.%может и длиннее, но маловероятно

\item Если ошибка произошла где-то в середине рида, то в графе появится короткий участок, представляющий альтернативный (приблизительно той же длины) путь между двумя вершинами графа (короткий ненаправленный цикл). 
Участок графа такого вида называют \textit{пузырем} (bulge, bubble). Одиночная ошибка, приводит к образованию ошибочного пути длины $k$, но так как ошибок в одном риде может быть несколько, то длина пузыря может достигать длины рида.

\item Химерному риду будет соответствовать короткий (длины порядка $k$) путь, соединяющий два ``далеких'' друг от друга участка графа (участки, скорее всего, ранее не связанные коротким путем).%, соответствующих различным участкам генома. 
Такие пути называют \textit{ошибочными соединениями} (erroneous connections). 
\end{itemize}

\textbf{Важное замечание.} Только из того, что участок имеет вид, похожий на тупик или пузырь, еще не означает, что он соответствует ошибке! 
Настоящие ребра, являющиеся тупиками, могут появляться из-за разрыва в покрытии генома. 
Пузырь может соответствовать неидеальному повтору (их в геноме великое множество).

Итак, одного вида окрестности недостаточно для того, чтобы принять решение об ошибочности участка.
Обычно, при решении об удалении того или иного участка, ассемблеры пользуются:
\begin{itemize}
\item величиной среднего покрытия ребер
\item последовательностями нуклеотидов ребер
\end{itemize}

\subsection{Обзор существующих ассемблеров}
Известные методы и идеи, лежащие в основе существующих алгоритмов сборки ДНК включают:

Далее приведен обзор нескольких (наиболее популярных) ассемблеров, основанных на графах де Брюина. Примеры ассемблеров, использующих другие подходы не приводятся, из-за того, что как было отмечено ранее, они не могут работать на интересующих нас входных данных. 

В связи с решаемой в данной работе задачей, особое внимание уделяется способам представления графа и устранения ошибочных участков, используемых в этих ассемблерах.

\subsubsection{Euler}
Первая версия разработана в 2000 году под руководством Павла Певзнера. Это первый ассемблер, использовавший подход, основанный на графах де Брюина. \cite{PT01, PTW01}
В то время произвел настоящую революцию и доказал возможность качественной сборки по коротким ридам.

За 10 лет было разработано большое количество версий этого ассемблера (Euler, Euler-DB, Euler$+$, Euler-SR), но в последние несколько лет, проект развивается не слишком активно. Текущая версия ассемблера, Euler-SR, вышла в 2008 году (\cite{CP08}).

Алгоритмы коррекции работают на сжатом графе де Брюина.

Все короткие ребра, один конец которых ``отсоединен'' от графа, удаляются как тупики.

Пузыри удаляются сложным методом, который в начале строит максимальное ветвление (maximum branching) графа и только затем устраняет короткие ненаправленные циклы, внимательно следя за тем, чтобы не удалить направленные циклы.

Все ребра с небольшим покрытием удаляются как ошибочные. 

\subsubsection{Velvet}
Разработан Дэниэлем Дзербино (\cite{VVT}). 

Изначально являлся набором инструментов для построения и упрощения графа де Брюина, построенного по ультра-коротким ридам (\cite{ZB08}). Позднее были добавлен модуль разрешения повторов с использованием парных или длинных одиночных ридов (\cite{ZMMB09}).

Использует оригинальное представление сжатого графа, в котором однозначные участки графа сжимаются не в длинные ребра, а длинные вершины.

Velvet также характерен тем, что он, в отличие, скажем, от Euler, в процессе коррекции графа уделяет много внимания поддержанию согласованности сопряженных элементов.

Тупик удаляется только если он имеют длину $<2k$ (достаточно распространенным среди ассемблеров пороговое значение), а также через место его ``крепления'' к графу проходит более покрытый путь.

Алгоритм удаления пузырей был назван Tour Bus. Схема его работы следующая. От произвольной вершины графа запускается алгоритм Дейкстры. В качестве весов при работе алгоритма рассматривается длина, деленная на значение покрытия. Таким образом алгоритм будет отдавать предпочтение путям с большим покрытием. Если алгоритм приходит в ранее посещенную вершину $a$, то он делает шаг на одну вершину и оказывается в $b$. После чего происходит поиск общего предка вершин $a$ и $b$ по отношению к рассмотренным путям. Если предок $c$ был найден не слишком далеко, то алгоритм анализирует похожесть последовательностей нуклеотидов, соответствующих путям $c \rightarrow a$ и $c \rightarrow b$. И если они оказываются похожи, то он запускает сложную процедуру слияния путей, не нарушающую согласованность сопряженных элементов графа, отдавая предпочтение тому пути, который был найден первым (более покрытому). Слияния не происходит, если оба пути имеют большое покрытие.

Сложность алгоритма Tour Bus составляет $O(N*log N)$, где $N$ - количество вершин графа.

Все короткие участки с небольшим покрытием удаляются как ошибочные. Важно, что этот шаг происходит после устранения тупиков и пузырей, когда большая часть таких участков, соответствовавшая реальным участкам генома, была ``включена'' в длинные вершины, в которых информация о покрытии усредняется.

\subsubsection{ALLPATHS}
Этот ассемблер является единственным из перечисленных здесь, который в явном виде не строит граф де Брюина целиком (\cite{BM08, AP2}).  %Подробное описание выходит за рамки этой работы.

Вместо этого он некоторым образом ``локализует'' риды, принадлежащие одному и тому же региону, после чего анализирует эти регионы отдельно друг от друга (при этом может делать это параллельно). Затем происходит этап ``склеивания'' локальных графов в единый граф. И только после этого происходит коррекция итогового графа.

На этапе корректирования не удаляет пузыри, удаляются только тупики.

Ошибочные соединения отдельно не удаляются, но из-за особенностей алгоритма, в итоговую сборку и так не попадут.

ALLPATHS, активно использует информацию о парных ридах. Более того, необходимым условием для использования этого ассемблера является наличие нескольких библиотек парных ридов со значительно отличающимся внутренним растоянием (в оригинальной статье использовались одновременно библиотеки с внутренним расстояниями 50 тыс, 6 тыс и 5 нуклеотидов).

\subsubsection{ABySS}
Ассемблер, использующий распределенное хранение несжатого графа де Брюина, при котором информация о различных $k$-мерах распределена по различным физическим машинах (\cite{SWJ09, ABYSS}). Позволяет осуществлять сборку больших геномов, используя сравнительно более дешевые компьютеры, объединенные в кластер (при этом из-за необходимости обмена сообщениями, скорость сборки в десятки раз ниже, чем, скажем, у SOAP \textit{de novo}).

Один из немногих ассемблеров, которому удалось осуществить\textit{de novo} сборку человеческого генома по NGS данным. Для этого использовался 21 компьютер, всего лишь с 16GB каждый.

Все алгоритмы коррекции работают на распределенном несжатом графе и распараллелены. Сжатый граф также строится, но уже после всех алгоритмов коррекции.

\subsubsection{SOAP \textit{de novo}}

Пожалуй, наиболее ``продвинутый'' из всех ассемблеров. Активно разрабатывается в Китае большой группой исследователей (\cite{SDN}).

Нацелен в первую очередь на сборку больших геномов (\cite{LZR10}).

Второй (помимо ABySS) ассемблер, способный за разумное время осуществлять \textit{de novo} сборку генома млекопитающих. Значительно выигрывает у ABySS в скорости, но требует для этого супер-компьютер с сотнями гигабайт оперативной памяти.

Недавно сего помощью была осуществлена \textit{de novo} сборка панды --- первого млекопитающего, собранного исключительно по коротким ридам.

По словам самих авторов, алгоритмы коррекции очень похожи на используемые в Velvet.

